package com.suanfa.demo;

import java.util.LinkedList;
import java.util.List;

public class sortUtils {
    /**
     * 折半查找（二分查找）
     * @param array
     * @param key
     * @return
     */
    public static int  halfCheck(int array[],int  key){
        int lo=0;
        int len=array.length -1;
        int mid;
        while(lo<=len){
            mid=(lo+len)/2;//向下取整（中位数）
            if(array[mid]==key){
                return mid;
            }else if (array[mid]>key){   //向左查找
                len=mid-1;
            }else {       //向右查找
                lo=mid+1;

            }
        }
        return -1;  //未从数组中找到匹配的值
    }

    /**
     * 冒泡排序
     * @param array
     */
    public static void MaoPaosort(int  array[]){
        int  n=array.length-1;
        int flag;
        for( int i=0;i<n;i++){
            for (int  j=0;j<n-i;j++){
                flag=0;               //变量flag用来标记本趟排序是否发生了交换
                if (array[j-1]>array[j]){
                        int  temp=array[j];
                        array[j]=array[j-1];
                        array[j-1]=temp;
                        flag=1;
                }
                if(flag==0){    //一趟排序过程中没有发生关键字交换，则证明序列有序，排序结束。
                    return;
                }
            }
        }
    }

    /**
     * 直接插入排序
     * @param array
     */
    public static void insertSort(int array[]){
        int n=array.length -1;
        int  i,index,intvarl;
        for(i=0;i<n;++i){
            intvarl=array[i];
            index=i-1;   //被插入的要比较的值
            while(index>=0&&array[index]>intvarl){
              array[index+1]=array[index];  //将array[index]往后移动一位
                index--;   //向前移动一位

            }
            array[index+1]=intvarl; //把插入的数放到合适的位置
        }

    }
    public static void QuicjSort(int array[] ,int low,int high){
        int temp;
        int i=low,j=high;
        if(low<high){
            temp=array[low];
            while(j<j){
                //从右到左开始扫描，找到一个比temp小的关键字
                while(j>i&&array[j]>=temp) --j;
                if(i<j){
                    array[i]=array[j];
                    ++i;
                }
                while(i<j&&array[i]<=temp) ++i;
                if (i<j){
                    array[j]=array[i];
                    --j;
                }
            }
            array[i]=temp; //将temp放在最终的位置
            QuicjSort(array,low,i-1);//递归对temp左边的光健字进行排序
            QuicjSort(array,i+1,high);//递归对temp右边的光健字进行排序
        }

    }
    public static void XirSort(int arr[]){
        int dk = arr.length/2;
        while(dk>=1){
            ShellSort(arr,dk);
            dk=dk/2;
        }
    }
    public static void ShellSort(int arr[],int dk){
        for (int i=dk;i<arr.length;++i){
            if(arr[i]<arr[i-dk]){
                int j;
                int a=arr[i]; //要被插入的值
                arr[i]=arr[i-dk];
                for(j=i-dk;j>=0&&a<arr[j];j=j-dk)
                    arr[j+dk]=arr[j];
                arr[j]=a;
            }
        }
    }

}
